package cxydmmszl.chapter02.t018;

import java.util.Stack;

/**
 * <li style="color: red;">Prob</li>
 * 判断一个链表是否为回文结构
 * <li style="color: red;">Desc</li>
 * 给定一个链表的头节点 head，请判断该链表是否文回文结构。<br/>
 * 例如：<br/>
 * &emsp;1->2->1，返回 true。<br/>
 * &emsp;1->2->2->1，返回 true。<br/>
 * &emsp;15->6->15，返回 true。<br/>
 * &emsp;1->2->3，返回 false。<br/>
 * <b>进阶：</b><br/>
 * 如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。
 * <li style="color: red;">Link</li> CD111、CD112
 *
 * @author habitplus
 * @since 2021-08-28 22:27
 */
public class Main {
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node reverseLinkedList(Node head) {
        Node pre = null;
        Node t;
        while (head != null) {
            t = head.next;
            head.next = pre;
            pre = head;
            head = t;
        }
        return pre;
    }

    public boolean isPalindrome(Node head) {
        Stack<Node> stack = new Stack<>();
        Node aux = head;
        while (aux != null) {
            stack.push(aux);
            aux = aux.next;
        }

        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public boolean isPalindrome01(Node head) {
        // 判断
        if (head == null || head.next == null) {
            return true;
        }

        // 找到中间节点
        Node p1 = head, p2 = head, mid = head; // mid -> 中间节点，主要用于恢复链表
        while (p2.next != null && p2.next.next != null) {
            mid = mid.next;
            p2 = p2.next.next;
        }

        // 从 p1 处断开
        p2 = mid.next;
        mid.next = null;

        // 反转右半区
        p2 = reverseLinkedList(p2);
        head = p2; // 暂存反转之后的头节点，用于恢复链表

        // 判断回文
        boolean res = true;
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) {
                res = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 恢复链表
        mid.next = reverseLinkedList(head);

        // 返回结果
        return res;
    }
}
